#include <stdio.h>
#include <math.h>
int number[210][5];
int select[110];
int array[4][5];
int count;
int selecount;
int larray[2][200];
int lcount[2];
void main()
{
    int i,k,flag,cc=0,i1,i4;
    printf(" There are magic squares with invertable primes as follow:\n");
    for(i=1001;i<9999;i+=2)
    {
        k=i/1000;
        if(k%2!=0 &&k!=5 &&num(i))
        {
            number[count][0]=i;
            process(count++);
            if(number[count-1][2]%2!=0 &&
                number[count-1][3]%2!=0 &&
                number[count-1][2]!=5 &&
                number[count-1][3]!=5)
                select[selecount++]=count -1;
        }
    }
    larray[0][lcount[0]++]==number[0][0]/100;
    larray[1][lcount[1]++]==number[0][0]/10;
    for(i=1;i<count;i++){
        if(larray[0][lcount[0]-1]!= number[i][0]/100)
            larray[0][lcount[0]++]=number[i][0]/100;
        if(larray[1][lcount[1]-1]!= number[i][0]/10)
            larray[1][lcount[1]++]=number[i][0]/10;
    }
    for (i1=0;i1<selecount;i1++){
        array[0][0]=select[i1];
        copy_num(0);
        for(array[1][0]=0;array[1][0]<count;array[1][0]++){
            copy_num(1);
            if(! comp_num(2))
            continue;
            for(array[2][0]=0;array[2][0]<count;array[2][0]++){
                copy_num(2);
                if(! comp_num(3))
                continue;
                for(i4=0;i4<selecount;i4++){
                    array[3][0]=select[i4];
                    copy_num(3);
                    for(flag=1,i=1;flag&&i<=4;i++)
                    if(! find1(i))flag=0;
                    if(flag&find2())
                    {printf("No.%d\n",++cc);p_array();}

                }
            }
        }
    }
}
num(int number)
{
    int j;
    if(! ok(number))return(0);
    for(j=0;number>0;number/=10)
    j=j*10+number%10;
    if(!ok(j))return(0);
    return(1);
}
ok(int number)
{
    int i,j;
    if(number %2==0)return(0);
    j=sqrt((double)number)+1;
    for(i=3;i<=j;i+=2)
    if(number %i==0)return(0);
    return(1);
}
process (int i)
{
    int j , num;
    num =number[i][0];
    for(j=4;j>=1;j--,num/=10)
    number[i][j]=num%10;
}
copy_num(int i)
{
    int j,num;
    num=number[i][0];
    for(j=4;j>=1;j--,num/=10)
    number[i][j]=num%10;
}
copy_num(int i)
{
    int j;
    for(j=1;j<=4;j++)
    array[i][j]=number[array[i][0]][j];
}
comp_num(int n)
{
    static int ii;
    static int jj;
    int i,num,k,*p;
    int *pcount;
    switch(n){
        case2:pcount=&lcount[0];p=&ii;break;
        case3:pcount=&lcount[1];p=&jj;break;
        default:return(0);
    }
    for (i=1;i<=4;i++)
    {
        for(num=0,k=0;k<n;k++)
            num=num*10+array[k][i];
        if(num<=array[n-2][*p])
            for(; *p>=0 && num<larray[n-2][*p];(*p)--);
        else 
            for(; *p<*pcount && num>larray[n-2][*p];(*p)++);
        if(*p<0 || *p>=*pcount){*p=0;return(0);}
        if(num !=larray[n-2][*p])
        return(0);
        }
        return(1);
    }
    find1(int i)
    {
        int num,j;
        for(num=0,j=0;j<4;j++) num = num *10+array[j][i];
        return(find0(num));
    }
    find2(void)
    {
        int num1,num2,j,i;
        for(num1=0,j=0;j<4;j++)
            num1=num1*10+array[j][j+1];
        for(num2=0,j=0,i=4;j<4;j++,i--)
            num2=num2*10+array[j][i];
        if(find0(num1))return(find0(num2));
        else return(0);
    }
    find0(int num)
    {
        static int j;
        if(num<=number[j][0])for(;j>=0&&num<number[j][0];j--);
        else for(;j<count && num>number[j][0];j++);
        if(j<0 || j>=count){j=0;return(0);}
        if(num ==number[j][0])return(1);
        else return(0);
    }
    p_array(void)
    {
        int i,j;
        for(i=0;i<4;i++){
            for(j=1;j<=4;j++)printf(" %6d",array[i][j]);
            printf("\n");
        }
    }
